//https://www.nowcoder.com/practice/6e5207314b5241fb83f2329e89fdecc8?tpId=13&tqId=23460&ru=%2Fpractice%2F389fc1c3d3be4479a154f63f495abff8&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13
// 重点！！！

#include <limits>
#include <vector>
#include <math.h>
#include <queue>
#include <map>

using namespace std;

class Solution {
public:
    int res=0;
    int cal(int n){
        int sum = 0;
        while(n){
            sum += (n % 10);
            n /= 10;
        }
        return sum;
    }
    void dfs(int threshold,int cur_row,int cur_col,int row,int col,vector<vector<bool>>& visited) {
        if (cur_row<0 || cur_row>=row || cur_col<0 ||cur_col>=col) {
            return;
        }
        auto row_bit_sum = cal(cur_row);
        auto col_bit_sum = cal(cur_col);
        if (row_bit_sum + col_bit_sum>threshold) return;

        if (visited[cur_row][cur_col]) return;

        ++res;
        visited[cur_row][cur_col]=true;
        //std::cout << cur_row << "," << cur_col << std::endl;

        dfs(threshold,cur_row-1,cur_col,row,col,visited);
        dfs(threshold,cur_row+1,cur_col,row,col,visited);
        dfs(threshold,cur_row,cur_col-1,row,col,visited);
        dfs(threshold,cur_row,cur_col+1,row,col,visited);

    }
    int movingCount(int threshold, int rows, int cols) {
        if (threshold < 0) return 0;
        vector<vector<bool>> visited_maxtrix(rows,vector<bool>(cols,false));

        dfs(threshold,0,0,rows,cols,visited_maxtrix);
        
        return res;
    }
};